home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 2: CDPD 1 / Almathera Ten on Ten - Disc 2: CDPD 1.iso / pd / 051-075 / 068 / mg1b / display.c < prev    next >
C/C++ Source or Header  |  1995-03-13  |  21KB  |  825 lines
  1. /*
  2.  * The functions in this file handle redisplay. The
  3.  * redisplay system knows almost nothing about the editing
  4.  * process; the editing functions do, however, set some
  5.  * hints to eliminate a lot of the grinding. There is more
  6.  * that can be done; the "vtputc" interface is a real
  7.  * pig. Two conditional compilation flags; the GOSLING
  8.  * flag enables dynamic programming redisplay, using the
  9.  * algorithm published by Jim Gosling in SIGOA. The MEMMAP
  10.  * changes things around for memory mapped video. With
  11.  * both off, the terminal is a VT52.
  12.  */
  13. #include    "def.h"
  14.  
  15. /*
  16.  * You can change these back to the types
  17.  * implied by the name if you get tight for space. If you
  18.  * make both of them "int" you get better code on the VAX.
  19.  * They do nothing if this is not Gosling redisplay, except
  20.  * for change the size of a structure that isn't used.
  21.  * A bit of a cheat.
  22.  */
  23. /* These defines really belong in sysdef.h */
  24. #ifndef XCHAR
  25. #  define    XCHAR    int
  26. #  define    XSHORT    int
  27. #endif
  28.  
  29. #ifdef    STANDOUT_GLITCH
  30. extern int SG;                /* number of standout glitches    */
  31. #endif
  32.  
  33. /*
  34.  * A video structure always holds
  35.  * an array of characters whose length is equal to
  36.  * the longest line possible. Only some of this is
  37.  * used if "ncol" isn't the same as "NCOL".
  38.  */
  39. typedef    struct    {
  40.     short    v_hash;            /* Hash code, for compares.    */
  41.     short    v_flag;            /* Flag word.            */
  42.     short    v_color;        /* Color of the line.        */
  43.     XSHORT    v_cost;            /* Cost of display.        */
  44.     char    v_text[NCOL];        /* The actual characters.    */
  45. }    VIDEO;
  46.  
  47. #define    VFCHG    0x0001            /* Changed.            */
  48. #define    VFHBAD    0x0002            /* Hash and cost are bad.    */
  49.  
  50. /*
  51.  * SCORE structures hold the optimal
  52.  * trace trajectory, and the cost of redisplay, when
  53.  * the dynamic programming redisplay code is used.
  54.  * If no fancy redisplay, this isn't used. The trace index
  55.  * fields can be "char", and the score a "short", but
  56.  * this makes the code worse on the VAX.
  57.  */
  58. typedef    struct    {
  59.     XCHAR    s_itrace;        /* "i" index for track back.    */
  60.     XCHAR    s_jtrace;        /* "j" index for trace back.    */
  61.     XSHORT    s_cost;            /* Display cost.        */
  62. }    SCORE;
  63.  
  64. int    sgarbf    = TRUE;            /* TRUE if screen is garbage.    */
  65. int    vtrow    = 0;            /* Virtual cursor row.        */
  66. int    vtcol    = 0;            /* Virtual cursor column.    */
  67. int    tthue    = CNONE;        /* Current color.        */
  68. int    ttrow    = HUGE;            /* Physical cursor row.        */
  69. int    ttcol    = HUGE;            /* Physical cursor column.    */
  70. int    tttop    = HUGE;            /* Top of scroll region.    */
  71. int    ttbot    = HUGE;            /* Bottom of scroll region.    */
  72.  
  73. VIDEO    *vscreen[NROW-1];        /* Edge vector, virtual.    */
  74. VIDEO    *pscreen[NROW-1];        /* Edge vector, physical.    */
  75. VIDEO    video[2*(NROW-1)];        /* Actual screen data.        */
  76. VIDEO    blanks;                /* Blank line image.        */
  77.  
  78. /*
  79.  * Some predeclerations to make ANSI compilers happy
  80.  */
  81. VOID    vtinit();
  82. VOID    vttidy();
  83. VOID    vtmove();
  84. VOID    vtputc();
  85. VOID    vteeol();
  86. VOID    update();
  87. VOID    ucopy();
  88. VOID    uline();
  89. VOID    modeline();
  90. VOID    hash();
  91. VOID    setscores();
  92. VOID    traceback();
  93.  
  94. #ifdef    GOSLING
  95. /*
  96.  * This matrix is written as an array because
  97.  * we do funny things in the "setscores" routine, which
  98.  * is very compute intensive, to make the subscripts go away.
  99.  * It would be "SCORE    score[NROW][NROW]" in old speak.
  100.  * Look at "setscores" to understand what is up.
  101.  */
  102. SCORE    score[NROW*NROW];
  103. #endif
  104.  
  105. /*
  106.  * Initialize the data structures used
  107.  * by the display code. The edge vectors used
  108.  * to access the screens are set up. The operating
  109.  * system's terminal I/O channel is set up. Fill the
  110.  * "blanks" array with ASCII blanks. The rest is done
  111.  * at compile time. The original window is marked
  112.  * as needing full update, and the physical screen
  113.  * is marked as garbage, so all the right stuff happens
  114.  * on the first call to redisplay.
  115.  */
  116. VOID
  117. vtinit() {
  118.     register VIDEO    *vp;
  119.     register int    i;
  120.  
  121.     ttopen();
  122.     ttinit();
  123.     vp = &video[0];
  124.     for (i=0; i<NROW-1; ++i) {
  125.         vscreen[i] = vp;
  126.         ++vp;
  127.         pscreen[i] = vp;
  128.         ++vp;
  129.     }
  130.     blanks.v_color = CTEXT;
  131.     for (i=0; i<NCOL; ++i)
  132.         blanks.v_text[i] = ' ';
  133. }
  134.  
  135. /*
  136.  * Tidy up the virtual display system
  137.  * in anticipation of a return back to the host
  138.  * operating system. Right now all we do is position
  139.  * the cursor to the last line, erase the line, and
  140.  * close the terminal channel.
  141.  */
  142. VOID
  143. vttidy() {
  144.     ttcolor(CTEXT);
  145.     ttnowindow();                /* No scroll window.    */
  146.     ttmove(nrow-1, 0);            /* Echo line.        */
  147.     tteeol();
  148.     tttidy();
  149.     ttflush();
  150.     ttclose();
  151. }
  152.  
  153. /*
  154.  * Move the virtual cursor to an origin
  155.  * 0 spot on the virtual display screen. I could
  156.  * store the column as a character pointer to the spot
  157.  * on the line, which would make "vtputc" a little bit
  158.  * more efficient. No checking for errors.
  159.  */
  160. VOID
  161. vtmove(row, col) {
  162.     vtrow = row;
  163.     vtcol = col;
  164. }
  165.  
  166. /*
  167.  * Write a character to the virtual display,
  168.  * dealing with long lines and the display of unprintable
  169.  * things like control characters. Also expand tabs every 8
  170.  * columns. This code only puts printing characters into 
  171.  * the virtual display image. Special care must be taken when
  172.  * expanding tabs. On a screen whose width is not a multiple
  173.  * of 8, it is possible for the virtual cursor to hit the
  174.  * right margin before the next tab stop is reached. This
  175.  * makes the tab code loop if you are not careful.
  176.  * Three guesses how we found this.
  177.  */
  178. VOID
  179. vtputc(c) register int c; {
  180.     register VIDEO    *vp;
  181.  
  182.     vp = vscreen[vtrow];
  183.     if (vtcol >= ncol)
  184.         vp->v_text[ncol-1] = '$';
  185.         else if (
  186. #ifdef    NOTAB
  187.          !(mode&MNOTAB) &&
  188. #endif
  189.          c == '\t') {
  190.         do {
  191.             vtputc(' ');
  192.         } while (vtcol<ncol && (vtcol&0x07)!=0);
  193.     } else if (ISCTRL(c) != FALSE) {
  194.         vtputc('^');
  195.         vtputc(c ^ 0x40);
  196.     } else
  197.         vp->v_text[vtcol++] = c;        
  198. }
  199.  
  200. /*
  201.  * Erase from the end of the
  202.  * software cursor to the end of the
  203.  * line on which the software cursor is
  204.  * located. The display routines will decide
  205.  * if a hardware erase to end of line command
  206.  * should be used to display this.
  207.  */
  208. VOID
  209. vteeol() {
  210.     register VIDEO    *vp;
  211.  
  212.     vp = vscreen[vtrow];
  213.     while (vtcol < ncol)
  214.         vp->v_text[vtcol++] = ' ';
  215. }
  216.  
  217. /*
  218.  * Make sure that the display is
  219.  * right. This is a three part process. First,
  220.  * scan through all of the windows looking for dirty
  221.  * ones. Check the framing, and refresh the screen.
  222.  * Second, make sure that "currow" and "curcol" are
  223.  * correct for the current window. Third, make the
  224.  * virtual and physical screens the same.
  225.  */
  226. VOID
  227. update() {
  228.     register LINE    *lp;
  229.     register WINDOW    *wp;
  230.     register VIDEO    *vp1;
  231.     VIDEO        *vp2;
  232.     register int    i;
  233.     register int    j;
  234.     register int    c;
  235.     register int    hflag;
  236.     register int    currow;
  237.     register int    curcol;
  238.     register int    offs;
  239.     register int    size;
  240.     VOID traceback ();
  241.     VOID uline ();
  242.  
  243.     if (typeahead()) return;
  244.     if (sgarbf) {                /* must update everything */
  245.         wp = wheadp; 
  246.         while(wp != NULL) {
  247.             wp->w_flag |= WFMODE | WFHARD;
  248.             wp = wp->w_wndp;
  249.         }
  250.     }
  251.     hflag = FALSE;                /* Not hard.        */
  252.     wp = wheadp;
  253.     while (wp != NULL) {
  254.         if (wp->w_flag != 0) {        /* Need update.        */
  255.             if ((wp->w_flag&WFFORCE) == 0) {
  256.                 lp = wp->w_linep;
  257.                 for (i=0; i<wp->w_ntrows; ++i) {
  258.                     if (lp == wp->w_dotp)
  259.                         goto out;
  260.                     if (lp == wp->w_bufp->b_linep)
  261.                         break;
  262.                     lp = lforw(lp);
  263.                 }
  264.             }
  265.             i = wp->w_force;    /* Reframe this one.    */
  266.             if (i > 0) {
  267.                 --i;
  268.                 if (i >= wp->w_ntrows)
  269.                     i = wp->w_ntrows-1;
  270.             } else if (i < 0) {
  271.                 i += wp->w_ntrows;
  272.                 if (i < 0)
  273.                     i = 0;
  274.             } else
  275.                 i = wp->w_ntrows/2;
  276.             lp = wp->w_dotp;
  277.             while (i!=0 && lback(lp)!=wp->w_bufp->b_linep) {
  278.                 --i;
  279.                 lp = lback(lp);
  280.             }
  281.             wp->w_linep = lp;
  282.             wp->w_flag |= WFHARD;    /* Force full.        */
  283.         out:
  284.             lp = wp->w_linep;    /* Try reduced update.    */
  285.             i  = wp->w_toprow;
  286.             if ((wp->w_flag&~WFMODE) == WFEDIT) {
  287.                 while (lp != wp->w_dotp) {
  288.                     ++i;
  289.                     lp = lforw(lp);
  290.                 }
  291.                 vscreen[i]->v_color = CTEXT;
  292.                 vscreen[i]->v_flag |= (VFCHG|VFHBAD);
  293.                 vtmove(i, 0);
  294.                 for (j=0; j<llength(lp); ++j)
  295.                     vtputc(lgetc(lp, j));
  296.                 vteeol();
  297.             } else if ((wp->w_flag&(WFEDIT|WFHARD)) != 0) {
  298.                 hflag = TRUE;
  299.                 while (i < wp->w_toprow+wp->w_ntrows) {
  300.                     vscreen[i]->v_color = CTEXT;
  301.                     vscreen[i]->v_flag |= (VFCHG|VFHBAD);
  302.                     vtmove(i, 0);
  303.                     if (lp != wp->w_bufp->b_linep) {
  304.                         for (j=0; j<llength(lp); ++j)
  305.                             vtputc(lgetc(lp, j));
  306.                         lp = lforw(lp);
  307.                     }
  308.                     vteeol();
  309.                     ++i;
  310.                 }
  311.             }
  312.             if ((wp->w_flag&WFMODE) != 0)
  313.                 modeline(wp);
  314.             wp->w_flag  = 0;
  315.             wp->w_force = 0;
  316.         }        
  317.         wp = wp->w_wndp;
  318.     }
  319.     lp = curwp->w_linep;            /* Cursor location.    */
  320.     currow = curwp->w_toprow;
  321.     while (lp != curwp->w_dotp) {
  322.         ++currow;
  323.         lp = lforw(lp);
  324.     }
  325.     curcol = 0;
  326.     i = 0;
  327.     while (i < curwp->w_doto) {
  328.         c = lgetc(lp, i++);
  329.                 if (
  330. #ifdef    NOTAB
  331.             !(mode&MNOTAB) &&
  332. #endif
  333.             c == '\t')
  334.             curcol |= 0x07;
  335.         else if (ISCTRL(c) != FALSE)
  336.             ++curcol;
  337.         ++curcol;
  338.     }
  339.     if (curcol >= ncol)            /* Long line.        */
  340.         curcol = ncol-1;
  341.     if (sgarbf != FALSE) {            /* Screen is garbage.    */
  342.         sgarbf = FALSE;            /* Erase-page clears    */
  343.         epresf = FALSE;            /* the message area.    */
  344.         tttop  = HUGE;            /* Forget where you set    */
  345.         ttbot  = HUGE;            /* scroll region.    */
  346.         tthue  = CNONE;            /* Color unknown.    */
  347.         ttmove(0, 0);
  348.         tteeop();
  349.         for (i=0; i<nrow-1; ++i) {
  350.             uline(i, vscreen[i], &blanks);
  351.             ucopy(vscreen[i], pscreen[i]);
  352.         }
  353.         ttmove(currow, curcol);
  354.         ttflush();
  355.         return;
  356.     }
  357. #ifdef    GOSLING
  358.     if (hflag != FALSE) {            /* Hard update?        */
  359.         for (i=0; i<nrow-1; ++i) {    /* Compute hash data.    */
  360.             hash(vscreen[i]);
  361.             hash(pscreen[i]);
  362.         }
  363.         offs = 0;            /* Get top match.    */
  364.         while (offs != nrow-1) {
  365.             vp1 = vscreen[offs];
  366.             vp2 = pscreen[offs];
  367.             if (vp1->v_color != vp2->v_color
  368.             ||  vp1->v_hash  != vp2->v_hash)
  369.                 break;
  370.             uline(offs, vp1, vp2);
  371.             ucopy(vp1, vp2);
  372.             ++offs;
  373.         }
  374.         if (offs == nrow-1) {        /* Might get it all.    */
  375.             ttmove(currow, curcol);
  376.             ttflush();
  377.             return;
  378.         }
  379.         size = nrow-1;            /* Get bottom match.    */
  380.         while (size != offs) {
  381.             vp1 = vscreen[size-1];
  382.             vp2 = pscreen[size-1];
  383.             if (vp1->v_color != vp2->v_color
  384.             ||  vp1->v_hash  != vp2->v_hash)
  385.                 break;
  386.             uline(size-1, vp1, vp2);
  387.             ucopy(vp1, vp2);
  388.             --size;
  389.         }
  390.         if ((size -= offs) == 0)    /* Get screen size.    */
  391.             panic("Illegal screen size in update");
  392.         setscores(offs, size);        /* Do hard update.    */
  393.         traceback(offs, size, size, size);
  394.         for (i=0; i<size; ++i)
  395.             ucopy(vscreen[offs+i], pscreen[offs+i]);
  396.         ttmove(currow, curcol);
  397.         ttflush();
  398.         return;            
  399.     }
  400. #endif
  401.     for (i=0; i<nrow-1; ++i) {        /* Easy update.        */
  402.         vp1 = vscreen[i];
  403.         vp2 = pscreen[i];
  404.         if ((vp1->v_flag&VFCHG) != 0) {
  405.             uline(i, vp1, vp2);
  406.             ucopy(vp1, vp2);
  407.         }
  408.     }
  409.     ttmove(currow, curcol);
  410.     ttflush();
  411. }
  412.  
  413. /*
  414.  * Update a saved copy of a line,
  415.  * kept in a VIDEO structure. The "vvp" is
  416.  * the one in the "vscreen". The "pvp" is the one
  417.  * in the "pscreen". This is called to make the
  418.  * virtual and physical screens the same when
  419.  * display has done an update.
  420.  */
  421. VOID
  422. ucopy(vvp, pvp) register VIDEO *vvp; register VIDEO *pvp; {
  423.  
  424.     vvp->v_flag &= ~VFCHG;            /* Changes done.    */
  425.     pvp->v_flag  = vvp->v_flag;        /* Update model.    */
  426.     pvp->v_hash  = vvp->v_hash;
  427.     pvp->v_cost  = vvp->v_cost;
  428.     pvp->v_color = vvp->v_color;
  429.     bcopy(vvp->v_text, pvp->v_text, ncol);
  430. }
  431.  
  432. /*
  433.  * Update a single line. This routine only
  434.  * uses basic functionality (no insert and delete character,
  435.  * but erase to end of line). The "vvp" points at the VIDEO
  436.  * structure for the line on the virtual screen, and the "pvp"
  437.  * is the same for the physical screen. Avoid erase to end of
  438.  * line when updating CMODE color lines, because of the way that
  439.  * reverse video works on most terminals.
  440.  */
  441. VOID uline(row, vvp, pvp) VIDEO *vvp; VIDEO *pvp; {
  442. #ifdef    MEMMAP
  443.     putline(row+1, 1, &vvp->v_text[0]);
  444. #else
  445.     register char    *cp1;
  446.     register char    *cp2;
  447.     register char    *cp3;
  448.     char        *cp4;
  449.     char        *cp5;
  450.     register int    nbflag;
  451.  
  452.     if (vvp->v_color != pvp->v_color) {    /* Wrong color, do a    */
  453.         ttmove(row, 0);            /* full redraw.        */
  454. #ifdef    STANDOUT_GLITCH
  455.         if (pvp->v_color != CTEXT && SG >= 0) tteeol();
  456. #endif
  457.         ttcolor(vvp->v_color);
  458. #ifdef    STANDOUT_GLITCH
  459.         cp1 = &vvp->v_text[SG > 0 ? SG : 0];
  460.         /* the odd code for SG==0 is to avoid putting the invisable
  461.          * glitch character on the next line.  
  462.          * (Hazeltine executive 80 model 30)
  463.          */
  464.         cp2 = &vvp->v_text[ncol - (SG >= 0 ? (SG!=0 ? SG : 1) : 0)];
  465. #else
  466.         cp1 = &vvp->v_text[0];
  467.         cp2 = &vvp->v_text[ncol];
  468. #endif
  469.         while (cp1 != cp2) {
  470.             ttputc(*cp1++);
  471.             ++ttcol;
  472.         }
  473. #ifndef    MOVE_STANDOUT
  474.         ttcolor(CTEXT);
  475. #endif
  476.         return;
  477.     }
  478.     cp1 = &vvp->v_text[0];            /* Compute left match.    */
  479.     cp2 = &pvp->v_text[0];
  480.     while (cp1!=&vvp->v_text[ncol] && cp1[0]==cp2[0]) {
  481.         ++cp1;
  482.         ++cp2;
  483.     }
  484.     if (cp1 == &vvp->v_text[ncol])        /* All equal.        */
  485.         return;
  486.     nbflag = FALSE;
  487.     cp3 = &vvp->v_text[ncol];        /* Compute right match.    */
  488.     cp4 = &pvp->v_text[ncol];
  489.     while (cp3[-1] == cp4[-1]) {
  490.         --cp3;
  491.         --cp4;
  492.         if (cp3[0] != ' ')        /* Note non-blanks in    */
  493.             nbflag = TRUE;        /* the right match.    */
  494.     }
  495.     cp5 = cp3;                /* Is erase good?    */
  496.     if (nbflag==FALSE && vvp->v_color==CTEXT) {
  497.         while (cp5!=cp1 && cp5[-1]==' ')
  498.             --cp5;
  499.         /* Alcyon hack */
  500.         if ((int)(cp3-cp5) <= tceeol)
  501.             cp5 = cp3;
  502.     }
  503.     /* Alcyon hack */
  504.     ttmove(row, (int)(cp1-&vvp->v_text[0]));
  505. #ifdef    STANDOUT_GLITCH
  506.     if (vvp->v_color != CTEXT && SG > 0) {
  507.         if(cp1 < &vvp->v_text[SG]) cp1 = &vvp->v_text[SG];
  508.         if(cp5 > &vvp->v_text[ncol-SG]) cp5 = &vvp->v_text[ncol-SG];
  509.     } else if (SG < 0)
  510. #endif
  511.     ttcolor(vvp->v_color);
  512.     while (cp1 != cp5) {
  513.         ttputc(*cp1++);
  514.         ++ttcol;
  515.     }
  516.     if (cp5 != cp3)                /* Do erase.        */
  517.         tteeol();
  518. #endif
  519. }
  520.  
  521. /*
  522.  * Redisplay the mode line for
  523.  * the window pointed to by the "wp".
  524.  * This is the only routine that has any idea
  525.  * of how the modeline is formatted. You can
  526.  * change the modeline format by hacking at
  527.  * this routine. Called by "update" any time
  528.  * there is a dirty window.
  529.  * Note that if STANDOUT_GLITCH is defined, first and last SG characters
  530.  * may never be seen.
  531.  */
  532. VOID
  533. modeline(wp) register WINDOW *wp; {
  534.     register int    n;
  535.     register BUFFER    *bp;
  536.  
  537.     n = wp->w_toprow+wp->w_ntrows;        /* Location.        */
  538.     vscreen[n]->v_color = CMODE;        /* Mode line color.    */
  539.     vscreen[n]->v_flag |= (VFCHG|VFHBAD);    /* Recompute, display.    */
  540.     vtmove(n, 0);                /* Seek to right line.    */
  541.     bp = wp->w_bufp;
  542.     vtputc('-'); vtputc('-');
  543.     if ((bp->b_flag&BFCHG) != 0) {        /* "*" if changed.    */
  544.         vtputc('*'); vtputc('*');
  545.     } else {
  546.         vtputc('-'); vtputc('-');
  547.     }
  548.     vtputc('-');
  549.     n  = 5;
  550.     n += vtputs("MicroGnuEmacs:");
  551.     if (bp->b_bname[0] != 0) {
  552.         vtputc(' ');
  553.         ++n;
  554.         n += vtputs(&(bp->b_bname[0]));
  555.     }
  556.     while (n < 42) {            /* Pad out with blanks    */
  557.         vtputc(' ');
  558.         ++n;
  559.     }
  560.     vtputc('(');
  561.     ++n;
  562.     if (mode == 0) n += vtputs("Fundamental");
  563.     else {
  564.         if ((mode&MBSMAP) != 0) {
  565.             n += vtputs("bsmap");
  566.             if ((mode&~MBSMAP) != 0) {
  567.                 vtputc('-');
  568.                 ++n;
  569.             }
  570.         }
  571.         if ((mode&MFLOW) != 0) {
  572.             n += vtputs("flow");
  573.             if ((mode&~(MFLOW|MBSMAP)) != 0) {
  574.                 vtputc('-');
  575.                 ++n;
  576.             }
  577.         }
  578. #ifdef    NOTAB
  579.         if ((mode&MNOTAB) != 0) {
  580.             n += vtputs("notab");
  581.             if ((mode&~(MINDENT|MNOTAB|MBSMAP)) != 0) {
  582.                 vtputc('-');
  583.                 ++n;
  584.             }
  585.         }
  586. #endif
  587.         if ((mode&MINDENT) != 0) {
  588.             n += vtputs("indent");
  589.                         if ((mode&~(MINDENT|MFLOW|MBSMAP
  590. #ifdef    NOTAB
  591.                             |MNOTAB
  592. #endif
  593.                             )) != 0) {
  594.                 vtputc('-');
  595.                 ++n;
  596.             }
  597.         }
  598.         if ((mode&MFILL) != 0)
  599.             n += vtputs("fill");
  600.     }
  601.     vtputc(')');
  602.     ++n;
  603.     while (n < ncol) {            /* Pad out.        */
  604.         vtputc('-');
  605.         ++n;
  606.     }
  607. }
  608. /*
  609.  * output a string to the mode line, report how long it was.
  610.  */
  611. vtputs(s) register char *s; {
  612.     register int n = 0;
  613.  
  614.     while (*s != '\0') {
  615.         vtputc(*s++);
  616.         ++n;
  617.     }
  618.     return n;
  619. }
  620. #ifdef    GOSLING
  621. /*
  622.  * Compute the hash code for
  623.  * the line pointed to by the "vp". Recompute
  624.  * it if necessary. Also set the approximate redisplay
  625.  * cost. The validity of the hash code is marked by
  626.  * a flag bit. The cost understand the advantages
  627.  * of erase to end of line. Tuned for the VAX
  628.  * by Bob McNamara; better than it used to be on
  629.  * just about any machine.
  630.  */
  631. VOID
  632. hash(vp) register VIDEO *vp; {
  633.     register int    i;
  634.     register int    n;
  635.     register char    *s;
  636.  
  637.     if ((vp->v_flag&VFHBAD) != 0) {        /* Hash bad.        */
  638.         s = &vp->v_text[ncol-1];
  639.         for (i=ncol; i!=0; --i, --s)
  640.             if (*s != ' ')
  641.                 break;
  642.         n = ncol-i;            /* Erase cheaper?    */
  643.         if (n > tceeol)
  644.             n = tceeol;
  645.         vp->v_cost = i+n;        /* Bytes + blanks.    */
  646.         for (n=0; i!=0; --i, --s)
  647.             n = (n<<5) + n + *s;
  648.         vp->v_hash = n;            /* Hash code.        */
  649.         vp->v_flag &= ~VFHBAD;        /* Flag as all done.    */
  650.     }
  651. }
  652.  
  653. /*
  654.  * Compute the Insert-Delete
  655.  * cost matrix. The dynamic programming algorithm
  656.  * described by James Gosling is used. This code assumes
  657.  * that the line above the echo line is the last line involved
  658.  * in the scroll region. This is easy to arrange on the VT100
  659.  * because of the scrolling region. The "offs" is the origin 0
  660.  * offset of the first row in the virtual/physical screen that
  661.  * is being updated; the "size" is the length of the chunk of
  662.  * screen being updated. For a full screen update, use offs=0
  663.  * and size=nrow-1.
  664.  *
  665.  * Older versions of this code implemented the score matrix by
  666.  * a two dimensional array of SCORE nodes. This put all kinds of
  667.  * multiply instructions in the code! This version is written to
  668.  * use a linear array and pointers, and contains no multiplication
  669.  * at all. The code has been carefully looked at on the VAX, with
  670.  * only marginal checking on other machines for efficiency. In
  671.  * fact, this has been tuned twice! Bob McNamara tuned it even
  672.  * more for the VAX, which is a big issue for him because of
  673.  * the 66 line X displays.
  674.  *
  675.  * On some machines, replacing the "for (i=1; i<=size; ++i)" with
  676.  * i = 1; do { } while (++i <=size)" will make the code quite a
  677.  * bit better; but it looks ugly.
  678.  */
  679. VOID
  680. setscores(offs, size) {
  681.     register SCORE    *sp;
  682.     SCORE        *sp1;
  683.     register int    tempcost;
  684.     register int    bestcost;
  685.     register int    j;
  686.     register int    i;
  687.     register VIDEO    **vp;
  688.     VIDEO        **pp, **vbase, **pbase;
  689.  
  690.     vbase = &vscreen[offs-1];        /* By hand CSE's.    */
  691.     pbase = &pscreen[offs-1];
  692.     score[0].s_itrace = 0;            /* [0, 0]        */
  693.     score[0].s_jtrace = 0;
  694.     score[0].s_cost   = 0;
  695.     sp = &score[1];                /* Row 0, inserts.    */
  696.     tempcost = 0;
  697.     vp = &vbase[1];
  698.     for (j=1; j<=size; ++j) {
  699.         sp->s_itrace = 0;
  700.         sp->s_jtrace = j-1;
  701.         tempcost += tcinsl;
  702.         tempcost += (*vp)->v_cost;
  703.         sp->s_cost = tempcost;
  704.         ++vp;
  705.         ++sp;
  706.     }
  707.     sp = &score[NROW];            /* Column 0, deletes.    */
  708.     tempcost = 0;
  709.     for (i=1; i<=size; ++i) {
  710.         sp->s_itrace = i-1;
  711.         sp->s_jtrace = 0;
  712.         tempcost  += tcdell;
  713.         sp->s_cost = tempcost;
  714.         sp += NROW;
  715.     }
  716.     sp1 = &score[NROW+1];            /* [1, 1].        */
  717.     pp = &pbase[1];
  718.     for (i=1; i<=size; ++i) {
  719.         sp = sp1;
  720.         vp = &vbase[1];
  721.         for (j=1; j<=size; ++j) {
  722.             sp->s_itrace = i-1;
  723.             sp->s_jtrace = j;
  724.             bestcost = (sp-NROW)->s_cost;
  725.             if (j != size)        /* Cd(A[i])=0 @ Dis.    */
  726.                 bestcost += tcdell;
  727.             tempcost = (sp-1)->s_cost;
  728.             tempcost += (*vp)->v_cost;
  729.             if (i != size)        /* Ci(B[j])=0 @ Dsj.    */
  730.                 tempcost += tcinsl;
  731.             if (tempcost < bestcost) {
  732.                 sp->s_itrace = i;
  733.                 sp->s_jtrace = j-1;
  734.                 bestcost = tempcost;
  735.             }
  736.             tempcost = (sp-NROW-1)->s_cost;
  737.             if ((*pp)->v_color != (*vp)->v_color
  738.             ||  (*pp)->v_hash  != (*vp)->v_hash)
  739.                 tempcost += (*vp)->v_cost;
  740.             if (tempcost < bestcost) {
  741.                 sp->s_itrace = i-1;
  742.                 sp->s_jtrace = j-1;
  743.                 bestcost = tempcost;
  744.             }
  745.             sp->s_cost = bestcost;
  746.             ++sp;            /* Next column.        */
  747.             ++vp;
  748.         }
  749.         ++pp;
  750.         sp1 += NROW;            /* Next row.        */
  751.     }
  752. }
  753.  
  754. /*
  755.  * Trace back through the dynamic programming cost
  756.  * matrix, and update the screen using an optimal sequence
  757.  * of redraws, insert lines, and delete lines. The "offs" is
  758.  * the origin 0 offset of the chunk of the screen we are about to
  759.  * update. The "i" and "j" are always started in the lower right
  760.  * corner of the matrix, and imply the size of the screen.
  761.  * A full screen traceback is called with offs=0 and i=j=nrow-1.
  762.  * There is some do-it-yourself double subscripting here,
  763.  * which is acceptable because this routine is much less compute
  764.  * intensive then the code that builds the score matrix!
  765.  */
  766. VOID traceback(offs, size, i, j) {
  767.     register int    itrace;
  768.     register int    jtrace;
  769.     register int    k;
  770.     register int    ninsl;
  771.     register int    ndraw;
  772.     register int    ndell;
  773.  
  774.     if (i==0 && j==0)            /* End of update.    */
  775.         return;
  776.     itrace = score[(NROW*i) + j].s_itrace;
  777.     jtrace = score[(NROW*i) + j].s_jtrace;
  778.     if (itrace == i) {            /* [i, j-1]        */
  779.         ninsl = 0;            /* Collect inserts.    */
  780.         if (i != size)
  781.             ninsl = 1;
  782.         ndraw = 1;
  783.         while (itrace!=0 || jtrace!=0) {
  784.             if (score[(NROW*itrace) + jtrace].s_itrace != itrace)
  785.                 break;
  786.             jtrace = score[(NROW*itrace) + jtrace].s_jtrace;
  787.             if (i != size)
  788.                 ++ninsl;
  789.             ++ndraw;
  790.         }
  791.         traceback(offs, size, itrace, jtrace);
  792.         if (ninsl != 0) {
  793.             ttcolor(CTEXT);
  794.             ttinsl(offs+j-ninsl, offs+size-1, ninsl);
  795.         }
  796.         do {                /* B[j], A[j] blank.    */
  797.             k = offs+j-ndraw;
  798.             uline(k, vscreen[k], &blanks);
  799.         } while (--ndraw);
  800.         return;
  801.     }
  802.     if (jtrace == j) {            /* [i-1, j]        */
  803.         ndell = 0;            /* Collect deletes.    */
  804.         if (j != size)
  805.             ndell = 1;
  806.         while (itrace!=0 || jtrace!=0) {
  807.             if (score[(NROW*itrace) + jtrace].s_jtrace != jtrace)
  808.                 break;
  809.             itrace = score[(NROW*itrace) + jtrace].s_itrace;
  810.             if (j != size)
  811.                 ++ndell;
  812.         }
  813.         if (ndell != 0) {
  814.             ttcolor(CTEXT);
  815.             ttdell(offs+i-ndell, offs+size-1, ndell);
  816.         }
  817.         traceback(offs, size, itrace, jtrace);
  818.         return;
  819.     }
  820.     traceback(offs, size, itrace, jtrace);
  821.     k = offs+j-1;
  822.     uline(k, vscreen[k], pscreen[offs+i-1]);
  823. }
  824. #endif
  825.